/**
 * //给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * //
 * // 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * //
 * // 此外，你可以假设该网格的四条边均被水包围。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：grid = [
 * //  ["1","1","1","1","0"],
 * //  ["1","1","0","1","0"],
 * //  ["1","1","0","0","0"],
 * //  ["0","0","0","0","0"]
 * //]
 * //输出：1
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：grid = [
 * //  ["1","1","0","0","0"],
 * //  ["1","1","0","0","0"],
 * //  ["0","0","1","0","0"],
 * //  ["0","0","0","1","1"]
 * //]
 * //输出：3
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // m == grid.length
 * // n == grid[i].length
 * // 1 <= m, n <= 300
 * // grid[i][j] 的值为 '0' 或 '1'
 * //
 * // Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 1785 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

public class ID00200NumberOfIslands {
    public static void main(String[] args) {

        Solution solution = new ID00200NumberOfIslands().new Solution();
        solution.numIslands(new char[][]{{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}});

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[][] visited = null;
        int totalNum = 0;
        int[][] differ = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //上下左右

        public int numIslands(char[][] grid) {

            int m = grid.length;
            int n = grid[0].length;
            visited = new boolean[m][n];

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (visited[i][j] || grid[i][j] == '0') {//该岛遍历过, 或者不是岛
                        continue;
                    } else {
                        totalNum++; //新发现岛屿
                        dfs(grid, m, n, new int[]{i, j});//所有岛屿的点都标记
                    }
                }
            }

            return totalNum;

        }

        public void dfs(char[][] grid, int m, int n, int[] nowPoint) {
            int x = nowPoint[0];//第几行
            int y = nowPoint[1];//第几列

            if (visited[x][y]) { //遍历过了
                return;
            }
            //没遍历过先标记
            visited[x][y] = true;

            for (int i = 0; i < differ.length; i++) { //上下左右四个分支
                int nextX = x + differ[i][0];
                int nextY = y + differ[i][1];
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] == '1') {
                    dfs(grid, m, n, new int[]{nextX, nextY});
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}